package com.zhangxiaofanfan.hotcode.first;

/**
 * <a href="https://leetcode.cn/problems/longest-palindromic-substring/?envType=study-plan-v2&envId=top-100-liked">5. 最长回文子串</a>
 *
 * @date 2024-07-13 03:14:13
 * @author zhangxiaofanfan
 */
public class HotCode093 {
    public static void main(String[] args) {
        HotCode093 hotCode = new HotCode093();
        System.out.println(hotCode.longestPalindrome("aaaaa"));
    }

    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }
        boolean[][] dp = new boolean[s.length()][s.length()];
        int left, right;
        String str = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        for (left = s.length() - 1; left >= 0; left--) {
            for (right = s.length() - 1; right > left; right--) {
                if (s.charAt(left) != s.charAt(right)) {
                    dp[left][right] = false;
                    continue;
                }
                if (left + 1 == right || left + 2 == right) {
                    dp[left][right] = true;
                } else {
                    dp[left][right] = dp[left + 1][right - 1];
                }
                if (dp[left][right] && (right - left + 1) > str.length()) {
                    str = s.substring(left, right + 1);
                }
            }
        }
        return str;
    }
}